#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "rangelist.h"

#define RANGE_ALLOC 5

static int allocate (rangelist_t *rangelist);

void rangelist_init (rangelist_t *rangelist)
{
	rangelist->ranges = NULL;
	rangelist->size = 0;
	rangelist->used = 0;
}

void rangelist_free (rangelist_t *rangelist)
{
	if (rangelist->ranges) {
		free (rangelist->ranges);
		rangelist->ranges = NULL;
	}

	rangelist->size = 0;
	rangelist->used = 0;
}

void rangelist_reset (rangelist_t *rangelist)
{
	rangelist->used = 0;
}

int rangelist_load (rangelist_t *rangelist, const char *string, size_t len, off_t filesize)
{
	/* Return values:
	 *  -1: Couldn't allocate memory.
	 * 200: Syntactically invalid byte-range-spec.
	 * 206: Partial Content.
	 * 416: Requested Range Not Satisfiable.
	 */

	off_t from;
	off_t to;
	off_t count;
	unsigned char c;
	size_t i;
	int state;
	int ret;

	/* RFC 2616
	 * http://www.faqs.org/rfcs/rfc2616.html
	 * 14.35.1 Byte Ranges
	 * The recipient of a byte-range-set that includes one or more syntactically
	 * invalid byte-range-spec values MUST ignore the header field that includes
	 * that byte-range-set.
	 */

	if (filesize <= 0) {
		return 200;
	}

	if ((len < sizeof ("bytes") - 1) || (strncasecmp (string, "bytes", 5) != 0)) {
		return 200;
	}

	/* Just to remove warnings... */
	from = 0;
	to = 0;
	count = 0;

	state = 0;

	for (i = sizeof ("bytes") - 1; i < len; i++) {
		c = (unsigned char) string[i];
		switch (state) {
			case 0:
				if (c == '=') {
					state = 1;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
			case 1:
				if ((c >= '0') && (c <= '9')) {
					from = c - '0';
					state = 2;
				} else if (c == '-') {
					state = 7;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
			case 2:
				if ((c >= '0') && (c <= '9')) {
					from = (from * 10) + (c - '0');
				} else if ((c == ' ') || (c == '\t')) {
					state = 3;
				} else if (c == '-') {
					state = 4;
				} else {
					return 200;
				}

				break;
			case 3:
				if (c == '-') {
					state = 4;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
			case 4:
				if ((c >= '0') && (c <= '9')) {
					to = c - '0';
					state = 5;
				} else if (c == ',') {
					to = filesize - 1;

					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 1;
				} else if ((c == ' ') || (c == '\t')) {
					to = filesize - 1;

					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 6;
				} else {
					return 200;
				}

				break;
			case 5:
				if ((c >= '0') && (c <= '9')) {
					to = (to * 10) + (c - '0');
				} else if (c == ',') {
					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 1;
				} else if ((c == ' ') || (c == '\t')) {
					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 6;
				} else {
					return 200;
				}

				break;
			case 6:
				if (c == ',') {
					state = 1;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
			case 7:
				if ((c >= '0') && (c <= '9')) {
					count = c - '0';
					state = 8;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
			case 8:
				if ((c >= '0') && (c <= '9')) {
					count = (count * 10) + (c - '0');
				} else if (c == ',') {
					if (count >= filesize) {
						from = 0;
						to = filesize - 1;
					} else {
						from = filesize - count;
						to = filesize - 1;
					}

					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 1;
				} else if ((c == ' ') || (c == '\t')) {
					if (count >= filesize) {
						from = 0;
						to = filesize - 1;
					} else {
						from = filesize - count;
						to = filesize - 1;
					}

					if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
						return ret;
					}

					state = 9;
				} else {
					return 200;
				}

				break;
			case 9:
				if (c == ',') {
					state = 1;
				} else if ((c != ' ') && (c != '\t')) {
					return 200;
				}

				break;
		}
	}

	switch (state) {
		case 0:
		case 1:
		case 2:
		case 3:
			return 200;
		case 4:
			to = filesize - 1;

			if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
				return ret;
			}

			break;
		case 5:
			if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
				return ret;
			}

			break;
		case 7:
			return 200;
		case 8:
			if (count >= filesize) {
				from = 0;
				to = filesize - 1;
			} else {
				from = filesize - count;
				to = filesize - 1;
			}

			if ((ret = rangelist_add_range (rangelist, from, to, filesize)) != 0) {
				return ret;
			}

			break;
	}

	if (rangelist->used == 0) {
		return 416;
	}

	return 206;
}

int allocate (rangelist_t *rangelist)
{
	range_t *ranges;
	size_t size;

	if (rangelist->used == rangelist->size) {
		size = rangelist->size + RANGE_ALLOC;
		ranges = (range_t *) realloc (rangelist->ranges, size * sizeof (range_t));
		if (!ranges) {
			return -1;
		}

		rangelist->ranges = ranges;
		rangelist->size = size;
	}

	return 0;
}

int rangelist_add_range (rangelist_t *rangelist, off_t from, off_t to, off_t filesize)
{
	/* Return values:
	 *  -1: Couldn't allocate memory.
	 *   0: Range added.
	 * 200: from > to.
	 */

	range_t *range;
	size_t from_pos, to_pos;
	size_t diff;
	int state;
	size_t i;

	if (from > to) {
		return 200;
	}

	if (from >= filesize) {
		return 0;
	}

	if (to >= filesize) {
		to = filesize - 1;
	}

	/* Just to remove warnings... */
	from_pos = 0;
	to_pos = 0;

	state = 0;

	for (i = 0; i < rangelist->used; i++) {
		range = &(rangelist->ranges[i]);

		if (state == 0) {
			if (from <= range->to + 1) {
				from_pos = i;

				if (to <= range->to + 1) {
					to_pos = i;

					state = 2; /* from_pos and to_pos are both initialized. */

					break;
				}

				state = 1; /* from_pos is initialized. */
			}
		} else {
			if (to <= range->to + 1) {
				to_pos = i;

				state = 2; /* from_pos and to_pos are both initialized. */

				break;
			}
		}
	}

	if (state == 0) {
		/* Last range. */

		if (allocate (rangelist) < 0) {
			return -1;
		}

		rangelist->ranges[i].from = from;
		rangelist->ranges[i].to = to;

		rangelist->used++;

		return 0;
	}

	if (state == 1) {
		/* 'to' is bigger than the biggest 'to'. */

		if (from < rangelist->ranges[from_pos].from) {
			rangelist->ranges[from_pos].from = from;
		}

		rangelist->ranges[from_pos].to = to;

		rangelist->used = from_pos + 1;

		return 0;
	}

	if (from_pos != to_pos) {
		/* Overlapping. */

		if (from < rangelist->ranges[from_pos].from) {
			rangelist->ranges[from_pos].from = from;
		}

		if (to + 1 < rangelist->ranges[to_pos].from) {
			to_pos--;
			rangelist->ranges[from_pos].to = to;
		} else {
			if (to >= rangelist->ranges[to_pos].to) {
				rangelist->ranges[from_pos].to = to;
			} else {
				rangelist->ranges[from_pos].to = rangelist->ranges[to_pos].to;
			}
		}

		if (from_pos != to_pos) {
			diff = rangelist->used - to_pos - 1;

			if (diff > 0) {
				memmove (&(rangelist->ranges[from_pos + 1]), &(rangelist->ranges[to_pos + 1]), diff * sizeof (range_t));
			}

			rangelist->used -= (to_pos - from_pos);
		}

		return 0;
	}

	if (to + 1 >= range->from) {
		if (from < range->from) {
			range->from = from;
		}

		if (to > range->to) {
			range->to = to;
		}

		return 0;
	}

	if (allocate (rangelist) < 0) {
		return -1;
	}

	memmove (&(rangelist->ranges[from_pos + 1]), &(rangelist->ranges[from_pos]), (rangelist->used - from_pos) * sizeof (range_t));

	range->from = from;
	range->to = to;

	rangelist->used++;

	return 0;
}

off_t rangelist_get_bytes (rangelist_t *rangelist)
{
	off_t bytes;
	size_t i;

	bytes = 0;
	for (i = 0; i < rangelist->used; i++) {
		bytes += (rangelist->ranges[i].to - rangelist->ranges[i].from + 1);
	}

	return bytes;
}

void rangelist_print (rangelist_t *rangelist)
{
	size_t i;

	printf ("Bytes: %lld.\n", rangelist_get_bytes (rangelist));

	for (i = 0; i < rangelist->used; i++) {
		printf ("Range: %lld-%lld\n", rangelist->ranges[i].from, rangelist->ranges[i].to);
	}
}
